HW#3 --- last modified February 07 2019 04:44:32..

Solution set.

Due date: Apr 17

Files to be submitted:
  Hw3.zip

Purpose: To practice the CFG, PDF, parsing algorithms learned in class as well as write down our first TMs.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO1 (Learning Outcome 1) -- Write a grammar for a language described otherwise.

LO7 -- Be able to use a pumping lemma to show that some languages are not regular and/or not context-free Use closure properties to simplify proofs of non-regularity of languages.

LO8 -- Be able to construct a pushdown automaton accepting a given language.

LO9 -- Construct a Turing machine accepting some simple languages.

Specification:

Group 1 (Must be handwritten, due start of class Mar. 20).

1. Give a 7-tuple for a PDA for the language `L={b^ka^nb^(2n) | n ge 0, k ge 0 }`.
2. Give a CFG for the language consisting of balanced parentheses. Use the algorithm from class to convert this CFG into a PDA. Show formally how this PDA would accept the string (()()).
3. Use the first algorithm from class to convert your PDA to a CFG.
4. Consider the language `L` consisting of all strings over `{0,1}` of the form `0^(2n)1^n0^n1^(2n)` for any `n ge 0`. Show using the pumping lemma this language is not context-free.

Group 2 (Must be handwritten, due start of class Apr. 3).

1. Show step-by-step how the string 0001010001 would be compressed by the SEQUITUR algorithm.
2. Draw a PDA for the language `L` over `{0,1}` consisting of strings with an equal number of `0`'s and `1`'s. So 010011 would be in this language. Next draw a DFA recognizing `0^star1^star`. Use the algorithm from class to draw a PDA for the intersection of these two languages.
3. Show step-by-step how the algorithm from class for checking if a language of CFG is infinite would operate on the grammar you got for problem (1) in this group.
4. Give the formal definition as a 6-tuple of a TM recognizing the string `{0^n1^n | n ge 0}` show formally that your machine accepts the string `000111`.

Group 3 (Must be handwritten, due start of class Apr. 17).

1. Consider ordered pairs `(v,w)` where w is an integer written in binary and `v = 3w` is written in binary. Draw a diagram of a TM which accepts only such ordered pairs.
2. Recall the definition of a grammar given during the Feb. 25 lecture. Prove that for a grammar `G` there is a TM recognizing the same language.
3. A Hyperspace TM is a single tape TM that operates on a semi-infinite tape (infinite to right not left). It acts like a normal TM except that rather than being able to do right moves it instead does "hyperjumps". A hyperjump moves the tape head to some non-deterministically chosen tape square on the tape. Such a situation might arise if the you had a normal machine, but the motors to move the tape in one direction slip or lurch. If your machine was in a remote location like Mars, it might be too costly to repair or replace it. A hyperspace TM, `M`, recognizes a string `x` if when started with `x` there is some computation of `M` (potentially involving hyperjumps) that leads to machine `M` accepting. Show if `L` is recognized by a usual TM, it can be recognized by a hyperspace TM.
4. Let `M` be a hyperspace TM. Prove that there is a usual TM that recognizes the same language.

For the online-submitted homework I would like you to do some experiments with JFLAP. As you do these experiments be mindful that you should try to keep image sizes small to ensure your file size will be under 2MB -- use a compressed image format. First, implement your PDA from Group 1 Problem 1 in JFLAP. Put it in the ZIP file as pda.jff. Add to the ZIP screenshots of stepping this PDA in JFLAP through the input baabbbb. Then using the 2nd algorithm from class, convert the PDA to a CFG. As a second experiment directly give a CFG for this language in JFLAP. Save this as grammar.jff . Then convert this CFG to a PDA in JFLAP. The next experiment I would like you to do is to try out the pumping lemma features in JFLAP. Pick a problem to pump for both the regular language setting and the CFL setting and give screenshots of going through and winning the two player game against the computer. Finally, I would like to build a TM in JFLAP which recognizes strings of the form: `1^n20^(lfloor n/3 rfloor)`. Put this in a file tm.jff and add screenshots showing it step through some inputs in JFLAP.

Point Breakdown